package main

import (
	"fmt"
	"math/rand"
)

func MergeSort(data []int) []int {
	if len(data) < 2 {
		return data
	}
	mid := len(data) / 2
	return Merge(MergeSort(data[:mid]), MergeSort(data[mid:]))

}
func Merge(left, right []int) []int {
	size := len(left) + len(right)
	i, j := 0, 0
	array := make([]int, size, size)

	for k := 0; k < size; k++ {
		if i < len(left) && j >= len(right) {
			array[k] = left[i]
			i++
		} else if i >= len(left) && j < len(right) {
			array[k] = right[j]
			j++
		} else if left[i] > right[j] {
			array[k] = right[j]
			j++
		} else {
			array[k] = left[i]
			i++
		}
	}
	return array

}

func main() {
	n := 100
	var data [10]int
	for i := 0; i < 10; i++ {
		data[i] = rand.Intn(n) + 1
	}
	fmt.Println("before merge data:", data)
	array := MergeSort(data[:10])
	fmt.Println("after merge:", array)
}
